package 笔试.深信服.搜索;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static int[][] dirs = {
            {-1, -1},    //左上
            {-1, 0},     //上
            {-1, 1},     //右上
            {0, -1},     //左
            {0, 1},      //右
            {1, -1},     //左下
            {1, 0},      //下
            {1, 1}       //右下
    };
    public static boolean[][] visited;

    public static void main(String[] args) {
        int n = 8;
        int[][] arr = {
                {0, 1, 1, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 1, 1, 0, 1},
                {1, 0, 1, 1, 0, 1, 1, 0},
                {0, 0, 0, 0, 1, 1, 0, 1},
                {0, 0, 1, 1, 0, 0, 0, 0},
                {1, 1, 0, 1, 0, 0, 1, 1},
                {1, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0}
        };
        visited = new boolean[n][n];
        Point start = new Point(0, 0, 0);
        visited[0][0] = true;
        int endX = 7;
        int endY = 7;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(start);
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            if (point.x == endX && point.y == endY) {
                System.out.println(point.step);
                break;
            }
            for (int[] dir : dirs) {
                int x = point.x + dir[0];
                int y = point.y + dir[1];
                if (x < 0 || x > n - 1 || y < 0 || y > n - 1) {
                    continue;
                }
                if (visited[x][y]) {
                    continue;
                }
                if (arr[x][y] == 0 && !visited[x][y]) {
                    queue.offer(new Point(x, y, point.step + 1));
                    visited[x][y] = true;
                }
            }
        }
    }
}

class Point {
    int x;
    int y;
    int step;

    public Point(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}
